
def merge_sort(nums):
    def merge(l,r):
        if len(l)==0: return r 
        if len(r)==0: return l 
        if l[0]<=r[0]:
            return [l[0]]+merge(l[1:],r)
        else:
            return [r[0]]+merge(l,r[1:])
    
    n = len(nums)
    if n<=1: return nums
    mid = n//2
    l = merge_sort(nums[:mid])
    r = merge_sort(nums[mid:])
    return merge(l,r)


def quick_sort(nums):
    def partition(nums,l,r):
        p = l
        i,j = l+1,l+1
        while j<=r:
            if nums[j]<nums[p]:
                nums[i],nums[j]=nums[j],nums[i]
                i+=1
            j+=1
        part = i-1
        nums[p],nums[part]=nums[part],nums[p]
        return part 
    
    def sort_main(nums,l,r):
        if l>=r: return nums
        p = partition(nums,l,r)
        sort_main(nums,l,p)
        sort_main(nums,p+1,r)
        return nums 
    
    sort_main(nums,0,len(nums)-1)
    return nums


nums = [2,1,3,6,7,5,9,8]
print(merge_sort(nums))
print(quick_sort(nums))

import numpy as np
def auc(y_true,y_pred):
    idx = np.argsort(y_pred)[::-1]
    y_true = y_true[idx]
    y_pred = y_pred[idx]
    pos,neg,k = 0,0,0
    i,n = 0,len(y_true)
    while i<n:
        j=i+1
        while j<n and y_pred[j]==y_pred[i]:
            j+=1
        pos_batch = np.sum(y_true[i:j])
        neg_batch = j-i-pos_batch 
        k += neg_batch*(0.5*pos_batch + pos)
        pos += pos_batch 
        neg += neg_batch 
        i = j 
    return k/(pos*neg)

y_true = np.array([1,1,0])
y_pred = np.array([0.5,0.5,0.6])
print(auc(y_true,y_pred))

y_true = np.array([1,1,0])
y_pred = np.array([0.5,0.7,0.6])
print(auc(y_true,y_pred))

y_true = np.array([1,1,0])
y_pred = np.array([0.5,0.7,0.5])
print(auc(y_true,y_pred))
    

